package com.example.demo.suanfa_heap;

import org.junit.Test;

/**
 * @program: java_base
 * @description: 堆结构简单示例
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/16 09:15
 */
public class HeapDemo {

    public int[] heap;
    private final int limit = 10 ;
    private int heapSize;

    public HeapDemo(){
        heap = new int[limit];
//        this.limit = limit;
        heapSize = 0;
    }

    public void push(int element){
        if (heapSize == limit){
            System.out.println("爆炸了");
            return;
        }
        heap[heapSize] = element;
        heapInsert(heap, heapSize++);
    }

    // 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉
    // 剩下的数，依然保持大根堆组织
    public int pop() {
        int maxValue = heap[0];
        /// 全局最大值，和 heap[index] 最大值替换；
        // 并且index-=1；使最大值 在数组最后，且取不到的位置。== 与数据逻辑断开连接
        swap(heap,0,--heapSize);
        heapify(heap, 0, heapSize);
        return maxValue;
    }

    // 新加进来的数，现在停在了index位置，请依次往上移动，
    // 移动到0位置，或者干不掉自己的父亲了，停！
    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int index, int i) {
        int tmp = arr[index];
        arr[index] = arr[i];
        arr[i] = tmp;
    }

    // 从index位置，往下看，不断的下沉
    // 停：较大的孩子都不再比index位置的数大；已经没孩子了
    private void heapify(int[] arr,int index,int heapSize){
        // 这个函数是，在保留arr[0]元素，arr[0] 和 arr[index]替换后，需要重新确定此大根堆的arr[0]位置的元素
        int leftIndex = index * 2 + 1;
        while (leftIndex < heapSize) {
            // 有向下走的趋势
            // 查看是否存在右节点 ，有孩子
            int maxIndex = index + 1 > heapSize ? index : index + 1;
            // 判断是选择左边得孩子？还是右边得孩子？// 是使用左边得？还是使用右边得index
            maxIndex = arr[leftIndex] > arr[maxIndex] ? leftIndex : maxIndex;
            // 判断 index 和 暂时得孩子节点得大小，确定 maxIndex
            maxIndex = arr[index] > arr[maxIndex] ? index : maxIndex;
            if (maxIndex == index){
                break;
            }
            if (arr[index] < arr[maxIndex]){
                swap(arr,index,maxIndex);
            }
            index = maxIndex;
            leftIndex = index * 2 + 1;
        }
    }

    @Test
    public  void  testTheHeap(){
        System.out.println(-3/2);
        System.out.println(3/2);

        HeapDemo heapDemo = new HeapDemo();
        for (int i = 0; i < 10; i++) {
            heapDemo.push(i);
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(heapDemo.pop());
        }

    }

}
